function Node(begin, end) {
    this.begin = begin;
    this.end = end;
    this.left = null;
    this.right = null;
    this.sum = 0; // 求区间和，还可以加min和max等区间极值
  }
// function build(begin, end, cb) {
//     var node = new Node(begin, end);
//     if (begin != end) { // 1+2 > 2
//       var mid = (begin + end) >> 1;
//       node.left = build(begin, mid, cb);
//       node.right = build(mid + 1, end, cb);
//     }
//     cb(node);
//     return node;
// }

// var array = [], unique = {};
// for (var i = 0; i < 8; i++) {
//   var el =  Math.floor(20 * Math.random());
//   if(unique[el]){
//     --i;
//   }else{
//     unique[el] = 1;
//     array.push(el);
//   }
// }
// console.log(JSON.stringify(array)); // [10,18,12,5,7,11,4,15] 

// 这样就可以在控制台中拿到这个数组
function build(begin, end, cb) {
  var node = new Node(begin, end);
  if (begin != end) { // 1+2 > 2
    var mid = (begin + end) >> 1;
    node.left = build(begin, mid, cb);
    node.right = build(mid + 1, end, cb);
  }
  cb( node);
  return node;
}
// class SegmentTree {
//   constructor(array) {
//     this.root = build(0, array.length - 1, function (node) {
//       if (node.begin === node.end) {
//         node.sum = array[node.end];
//       } else {
//         node.sum = node.left.sum + node.right.sum;
//       }
//     });
//   }
//   inOrder(){}
//   printNodeByLevel(){}
//   toString(){}
// }
// var t = new SegmentTree([10,18,12,5,7,11,4,15]);
// console.log(t+""); // 自行根据第5章实现toString等方法

// 8.1.2　单点查询
class SegmentTree {
    constructor(array) {
        this.root = build(0, array.length - 1, function (node) {
        if (node.begin === node.end) {
            node.sum = array[node.end];
        } else {
            node.sum = node.left.sum + node.right.sum;
        }
        });
    }
    inOrder(){}
    printNodeByLevel(){}
    toString(){}
    get(k){
        return queryOne(this.root, k);
    }
    add(k, delta){
        return updateOne(this.root, k, delta);
    }
    set(k, value){
        var diff = value - this.get(k);
        return updateOne(this.root, k, diff);
    }
    // querySum(x, y){
    //     return queryRange(this.root, x, y);
    // }
    querySum(x, y, delta){
        return updateRange(this.root, x, y, delta);
    }
}
  function queryOne(node, k) {
    if (!node) {
      return 0;
    }
    if (node.begin == k && node.end == k) {
      // 如果查询区间覆盖了当前结点
      return node.sum;
    }
    var mid = node.begin + ((node.end - node.begin) >> 1);
    if (k <= mid) {
      // 如果查询到结点的左孩子结点的范围
      return queryOne(node.left, k);
    } else if (k > mid) {
      return queryOne(node.right, k);
    }
  }
  function updateOne(node, k, delta) { // 对k位置的值，加上delta
    if (!node) {
      return 0;
    }
    if (node.begin == node.end && node.begin == k) { 
      return node.sum += delta;                             // 对该点的值进行操作，可以为+、-、*、/等
    }else{
      var mid = node.begin + ((node.end - node.begin) >> 1);// 判断该点在左区间还是右区间
      if (k <= mid) {// 左子树
        updateOne(node.left, k, delta);
      } else {// 右子树
        updateOne(node.right, k, delta);
      }
      // 会影响到它的父结点的sum
      return node.sum = node.left.sum + node.right.sum;
    }
}
function queryRange(node, x, y) {
    if (!node) {
      return 0;
    }
    if (node.begin == x && node.end == y) {
      // 如果查询区间覆盖了当前结点
      return node.sum;
    } else {
      var mid = node.begin + ((node.end - node.begin) >> 1);
      if (y <= mid) {// 如果查询区间在mid左边，因为x<y<=mid
        return queryRange(node.left, x, y);
      } else if (x > mid) {// 如果查询区间在mid右边，因为mid<x<y
        return queryRange(node.right, x, y);
      } else {
        return queryRange(node.left, x, mid) + 
               queryRange(node.right, mid + 1, y);
      }
    }
}
function updateRange(node, x, y, delta) { // 设区间为[x,y]，修改的值为k
    if (!node) {
      return 0;
    }
    if (node.begin == node.end && node.begin == x) {  // 如果是这个区间内的元素，就让它+delta
      return node.sum += delta;
    } else {
      var mid = node.begin + ((node.end - node.begin) >> 1);    // 判断该点在左区间还是右区间
      if (y <= mid) {// 如果区间在中值的左侧
        return node.sum = updateRange(node.left, x, y, delta) +
              (Object(node.right).sum || 0);
      } else if (x > mid) {// 如果区间在中值的右侧
        return node.sum = updateRange(node.right, x, y, delta) +
              (Object(node.left).sum || 0);
      } else {
        // 如果区间被中值分开
        return node.sum = updateRange(node.left, x, mid, delta) +
          updateRange(node.right, mid + 1, y, delta);
      }
    }
}
  var t = new SegmentTree([10,18,12,5,7,11,4,15]);
  console.log(t.get(7), 'get'); // 15
  console.log(t.add(7, 4), 'add');// 86
  // console.log(t.set(7, 4), 'set');// 71
  // console.log(t.querySum(2, 7),'querySum'); // 43

console.log(t.root.sum); // 86
console.log(t.querySum( 4, 7, 3), 'rangeAdd');
// 98 = 86+ (7-4+1) * 3


// // 8.1.6　延迟标记

// // function pushDown(node) {
// //     if (node.sumTag !== 0) {
// //       // 设置左结点的sumTag，因为孩子结点可能被多次延迟标记又没有向下传递
// //       // 所以是+=
// //       if (node.left) {
// //         node.left.sumTag += node.sumTag;
// //         // 根据sumTag设置孩子结点的值
  
// //         // 因为我们是求区间和，因此当区间内每个结点加上一个值时，区间的sum也加上这个值
// //         node.left.sum += node.sumTag;
// //       }
// //       if (node.right) {
// //         node.right.sumTag += node.sumTag;
// //         node.right.sum += node.sumTag;
// //       }
// //       // 传递后，当前结点标的sumTag清空
// //       node.sumTag = 0;
// //     }
// // }

// // function Node(begin, end) {
// //     this.begin = begin;
// //     this.end = end;
// //     this.left = null;
// //     this.right = null;
// //     this.sum = 0;
// //     this.sumTag = 0;
// // }

// // function queryRange(node, x, y) {
// //     if (!node) {
// //       return 0;
// //     }
// //     if(node.sumTag != 0){
// //       pushDown(node);// 校正当前结点的数据，如果下一行刚好命中，就不用处理孩子结点 
// //     }
// //     if (node.begin == x && node.end == y) {
// //       // 如果查询区间覆盖了当前结点
// //       return node.sum;
// //     }
// //     var mid = node.begin + ((node.end - node.begin) >> 1);
// //     if (y <= mid) {// 如果查询区间在mid左边，因为x<y<=mid
// //       return queryRange(node.left, x, y);
// //     } else if (x > mid) {// 如果查询区间在mid右边，因为mid<x<y
// //       return queryRange(node.right, x, y);
// //     } else {
// //       return queryRange(node.left, x, mid) + 
// //              queryRange(node.right, mid + 1, y);
// //     }  
// // }

// // function updateRange(node, x, y, delta) { // 设区间为[x,y]，修改的值为k
// //     if (!node) {
// //         return 0;
// //     }
// //     if(node.sumTag !== 0){
// //         pushDown(node);
// //     }
// //     if (node.begin == x && node.end == y) {  // 如果是这个区间内的元素，就让它+delta
// //         node.sumTag += delta;
// //         return node.sum += delta * (y-x+1);
// //     }
// //     if (node.begin == node.end && node.begin == x) {  // 如果是这个区间内的元素，就让它+delta
// //       return node.sum += delta;
// //     } else {
// //       var mid = node.begin + ((node.end - node.begin) >> 1);    // 判断该点在左区间还是右区间
// //       if (y <= mid) {// 如果区间在中值的左侧
// //         return node.sum = updateRange(node.left, x, y, delta) +
// //               (Object(node.right).sum || 0);
// //       } else if (x > mid) {// 如果区间在中值的右侧
// //         return node.sum = updateRange(node.right, x, y, delta) +
// //               (Object(node.left).sum || 0);
// //       } else {
// //         // 如果区间被中值分开
// //         return node.sum = updateRange(node.left, x, mid, delta) +
// //           updateRange(node.right, mid + 1, y, delta);
// //       }
// //     }
// // }

// var sum = [], m = 1;
// function build(n, array) {
//   // 构建一个满二叉树，并且保证最后一层的结点数必须多于n+2个
//   while (m <= n + 2) m <<= 1;
//   sum = new Array(m + m).fill(0);
//   // 还是刚才区间求和的问题，定义一个sum数组，默认都是0
//   for (var i = m + 1; i <= m + n; i++) {
//     sum[i] = array[i - m - 1];
//   }
//   for (var i = m - 1; i; i--) {// 自底向上求和
//     sum[i] = sum[i << 1] + sum[(i << 1) + 1];// 后面的也可以写成sum[i<<1|1]
//   }
// }
// var array = [10, 18, 12, 5, 7, 11, 4, 15];
// build(array.length, array);
// // console.log(sum.concat());


// // 8.2.2　单点查询

// function queryOne(k){// k从1算起
//     return sum[k+m];
//   }
//   console.log(queryOne(1)); // 10，原数组的第1个元素，从1数起
//   console.log(queryOne(2)); // 18，原数组的第2个元素，从1数起

// // 8.2.3　单点修改
// function updateOne(k, value){
//     for(var i=k+m;i;i>>=1){
//       sum[i]+=value;
//     }
//   }
//   updateOne(2, 4);// 第2个元素加上4
// //   console.log(sum[1]); // 82--> 86

// //   8.2.4　区间查询

// function queryRangeSum(s, t) {
//     var rangeSum = 0;
//     for (s += m - 1, t += m + 1; s ^ t ^ 1; s >>= 1, t >>= 1) {
//       if (~s & 1) {
//         rangeSum += sum[s ^ 1];  // sum[s^1]是sum[s]的兄弟 
//       }
//       if (t & 1) {
//         rangeSum += sum[t ^ 1]; // sum[t^1]是sum[t]的兄弟 
//       }
//     }
//     return rangeSum;
// }
// console.log(queryRangeSum(2, 5)); // 46 === 22 + 12 + 5 + 7 ，因为18在前面已经加4了


// // 8.3　标记永久化技巧
// function updateRange(s, t, delta) {
//   var add = new Array(m + m).fill(0);
//   var lcnt = 0, rcnt = 0, cnt = 1;
//   for (s = m + s - 1, t = m + t + 1; s ^ t ^ 1; s >>= 1, t >>= 1, cnt <<= 1) {
//     sum[s] += delta * lcnt;
//     sum[t] += delta * rcnt;
//     if (~s & 1) {
//       add[s ^ 1] += delta;
//       sum[s ^ 1] += delta * cnt;
//       lcnt += cnt;
//     }
//     if (t & 1) {
//       add[t ^ 1] += delta;
//       sum[t ^ 1] += delta * cnt;
//       rcnt += cnt;
//     }
//   }
//   while (s || t) {
//     sum[s] += delta * lcnt;
//     sum[t] += delta * rcnt;
//     s >>= 1;
//     t >>= 1;
//   }
// }

// updateRange(1,5, 3); 
// console.log(sum[1]);// 101 === 86 + 5*3

// // 8.3.2　基于标记永久化的区间查询
// function queryRange(s, t) {
//     var add = new Array(m + m).fill(0);
//     var lcnt = 0, rcnt = 0, cnt = 1, res = 0;
//     for (s = m + s - 1, t = m + t + 1; s ^ t ^ 1; s >>= 1, t >>= 1, cnt <<= 1) {
//       if (add[s]) res += add[s] * lcnt;
//       if (add[t]) res += add[t] * rcnt;
  
//       if (~s & 1) {
//         res += sum[s ^ 1];
//         lcnt += cnt;
//       }
//       if (t & 1) {
//         res += sum[t ^ 1];
//         rcnt += cnt;
//       }
//     }
//     while (s || t) {
//       res += add[s] * lcnt;
//       res += add[t] * rcnt;
//       s >>= 1;
//       t >>= 1;
//     }
//     return res;
//   }
//   console.log(queryRange(1, 5)); // 10+22+12+5+7 = 56 + 15 = 71


// 8.4　差分思想
// var min = [], max =[], m = 1;
// function build(n, array) {
//   // 构建一个满二叉树，并且保证最后一层的结点数必须多于n+2个
//   while (m <= n + 2) m <<= 1;
//   min = new Array(m + m).fill(Infinity);
//   max = new Array(m + m).fill(-Infinity);
//   // 还是刚才区间求和的问题，定义一个sum数组，默认都是0
//   for (var i = m + 1; i <= m + n; i++) {
//     min[i] = array[i - m - 1];
//     max[i] = array[i - m - 1];
//   }
//   for (var i = m - 1; i; i--) {// 自底向上求和
//     min[i] = Math.min(min[i << 1] , min[i << 1|1] );
//     min[i<<1] -= min[i];
//     min[i<<1|1] -= min[i];
    
//     max[i] = Math.max(max[i << 1] , max[i << 1|1] );
    
//     max[i<<1] -= max[i];
//     max[i<<1|1] -= max[i];
//   }
// }
// var array = [10, 18, 12, 5, 7, 11, 4, 15];
// build(array.length, array);
// console.log(min.concat(), max.concat() );

// // 8.4.1　基于差分思想的区间修改
// function updateRange(s, t, delta) {
//     var temp = 0;
//     for (s = m + s - 1, t = m + t + 1; s ^ t ^ 1; s >>= 1, t >>= 1) {
//       if (~s & 1) {
//         max[s ^ 1] += delta;
//       }
//       if (t & 1) {
//         max[t ^ 1] += delta;
//       }
//       temp = Math.max(max[s], max[s ^ 1]);
//       max[s] -= temp;
//       max[s ^ 1] -= temp; // 兄弟结点
//       max[s >> 1] += temp; // 父结点
  
//       temp = Math.max(max[t], max[t ^ 1]);
//       max[t] -= temp;
//       max[t ^ 1] -= temp; // 兄弟结点
//       max[t >> 1] += temp; // 父结点
  
//     }
//     while (s > 1) {
//       temp = Math.max(max[s], max[s ^ 1]);
//       max[s] -= temp; // 父结点
//       max[s ^ 1] -= temp; // 兄弟结点
//       max[s >> 1] += temp; // 父结点
//       s >>= 1;
//     }
//   }
//   updateRange(1, 5, 3)
//   console.log(max[1]) // 21

// //   8.4.2　基于差分思想的区间查询 
// function queryRange(s, t) { // 闭区间
//     var sAns = 0, tAns = 0;
//     s += m + 1, t += m - 1;
//     if (s != t) { // 防止查询单点时死循环
//       for (; s ^ t ^ 1; s >>= 1, t >>= 1) {
//         sAns += max[s]; tAns += max[t];
//         if (~s & 1) sAns = Math.min(sAns, max[s ^ 1]);
//         if (t & 1) tAns = Math.min(tAns, max[t ^ 1]);
//       }
//     }
//     var ans = Math.min(sAns + max[s], tAns + max[t]);
//     while (s > 1) ans += max[s >>= 1];
//     return ans;
//   }
//   console.log(queryRange(1, 3));// 21
//   console.log(queryRange(2, 4));// 15